

<!DOCTYPE html>
<html lang="zh-CN" data-default-color-scheme=&#34;auto&#34;>



<head>
  <meta charset="UTF-8">
  <link rel="apple-touch-icon" sizes="76x76" href="/blog/img/favicon.png">
  <link rel="icon" type="image/png" href="/blog/img/favicon.png">
  <meta name="viewport"
        content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no, shrink-to-fit=no">
  <meta http-equiv="x-ua-compatible" content="ie=edge">
  
    <meta http-equiv="Content-Security-Policy" content="upgrade-insecure-requests">
  
  <meta name="theme-color" content="#fff">
  <meta name="description" content="その時を待つよ">
  <meta name="author" content="Isshiki_Hugh">
  <meta name="keywords" content="">
  <title>algorithm-dp动态规划专题 - Isshiki&#39;sBlog</title>

  <link  rel="stylesheet" href="https://cdn.staticfile.org/twitter-bootstrap/4.4.1/css/bootstrap.min.css" />


  <link  rel="stylesheet" href="https://cdn.staticfile.org/github-markdown-css/4.0.0/github-markdown.min.css" />
  <link  rel="stylesheet" href="/blog/lib/hint/hint.min.css" />

  
    
    <link  rel="stylesheet" href="https://cdn.staticfile.org/highlight.js/10.0.0/styles/atom-one-dark.min.css" />
  

  


<!-- 主题依赖的图标库，不要自行修改 -->

<link rel="stylesheet" href="//at.alicdn.com/t/font_1749284_6peoq002giu.css">



<link rel="stylesheet" href="//at.alicdn.com/t/font_1736178_pjno9b9zyxs.css">


<link  rel="stylesheet" href="/blog/css/main.css" />

<!-- 自定义样式保持在最底部 -->


  <script  src="/blog/js/utils.js" ></script>
  <script  src="/blog/js/color-schema.js" ></script>
<meta name="generator" content="Hexo 5.0.2"></head>


<body>
  <header style="height: 75vh;">
    <nav id="navbar" class="navbar fixed-top  navbar-expand-lg navbar-dark scrolling-navbar">
  <div class="container">
    <a class="navbar-brand"
       href="/blog/">&nbsp;<strong>Isshiki修のBlog</strong>&nbsp;</a>

    <button id="navbar-toggler-btn" class="navbar-toggler" type="button" data-toggle="collapse"
            data-target="#navbarSupportedContent"
            aria-controls="navbarSupportedContent" aria-expanded="false" aria-label="Toggle navigation">
      <div class="animated-icon"><span></span><span></span><span></span></div>
    </button>

    <!-- Collapsible content -->
    <div class="collapse navbar-collapse" id="navbarSupportedContent">
      <ul class="navbar-nav ml-auto text-center">
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/blog/">
                <i class="iconfont icon-home-fill"></i>
                首页
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/blog/archives/">
                <i class="iconfont icon-archive-fill"></i>
                归档
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/blog/categories/">
                <i class="iconfont icon-category-fill"></i>
                分类
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/blog/tags/">
                <i class="iconfont icon-tags-fill"></i>
                标签
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/blog/about/">
                <i class="iconfont icon-user-fill"></i>
                关于
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/blog/links/">
                <i class="iconfont icon-link-fill"></i>
                友链
              </a>
            </li>
          
        
        
          <li class="nav-item" id="search-btn">
            <a class="nav-link" data-toggle="modal" data-target="#modalSearch">&nbsp;<i
                class="iconfont icon-search"></i>&nbsp;</a>
          </li>
        
        
          <li class="nav-item" id="color-toggle-btn">
            <a class="nav-link" href="javascript:">&nbsp;<i
                class="iconfont icon-dark" id="color-toggle-icon"></i>&nbsp;</a>
          </li>
        
      </ul>
    </div>
  </div>
</nav>

    <div class="banner intro-2" id="background" parallax=true
         style="background: url('/blog/img/default.JPG') no-repeat center center;
           background-size: cover;">
      <div class="full-bg-img">
        <div class="mask flex-center" style="background-color: rgba(0, 0, 0, 0.3)">
          <div class="container page-header text-center fade-in-up">
            <span class="h2" id="subtitle">
              
            </span>

            
              
  <div class="mt-3 post-meta">
    <i class="iconfont icon-date-fill" aria-hidden="true"></i>
    <time datetime="2019-11-07 09:27" pubdate>
      2019年11月7日 上午
    </time>
  </div>


<div class="mt-1">
  
    
    <span class="post-meta mr-2">
      <i class="iconfont icon-chart"></i>
      5k 字
    </span>
  

  
    
    <span class="post-meta mr-2">
      <i class="iconfont icon-clock-fill"></i>
      
      
      85
       分钟
    </span>
  

  
  
    
      <!-- 不蒜子统计文章PV -->
      <span id="busuanzi_container_page_pv" style="display: none">
        <i class="iconfont icon-eye" aria-hidden="true"></i>
        <span id="busuanzi_value_page_pv"></span> 次
      </span>
    
  
</div>

            
          </div>

          
        </div>
      </div>
    </div>
  </header>

  <main>
    
      

<div class="container-fluid">
  <div class="row">
    <div class="d-none d-lg-block col-lg-2"></div>
    <div class="col-lg-8 nopadding-md">
      <div class="container nopadding-md" id="board-ctn">
        <div class="py-5" id="board">
          <article class="post-content mx-auto" id="post">
            <!-- SEO header -->
            <h1 style="display: none">algorithm-dp动态规划专题</h1>
            
              <p class="note note-info">
                
                  本文最后更新于：1 年前
                
              </p>
            
            <div class="markdown-body" id="post-body">
              <h2 id="0-x-前言"><a href="#0-x-前言" class="headerlink" title="[0.x]前言"></a>[0.x]前言</h2><p>参考书目：<strong>《算法竞赛进阶指导》</strong></p>
<p>语言：$Cpp$</p>
<a id="more"></a>
<h2 id="目录"><a href="#目录" class="headerlink" title="目录"></a>目录</h2><ul>
<li>[0.x]前言</li>
<li>[1.x]线性dp</li>
<li>[2.x]背包</li>
<li>[3.x]区间dp</li>
<li><strong>[4.x]树形dp</strong>★</li>
<li>[5.x]环形与后效性处理</li>
<li>[6.x]状压dp</li>
<li>[7.x]倍增优化dp</li>
<li>[8.x]数据结构优化dp</li>
<li>[9.x]单调队列优化dp</li>
</ul>
<hr>
<h2 id="1-x-线性dp"><a href="#1-x-线性dp" class="headerlink" title="[1.x]线性dp"></a>[1.x]线性dp</h2><h3 id="1-1-最长上升序列-LIS-问题"><a href="#1-1-最长上升序列-LIS-问题" class="headerlink" title="[1.1]最长上升序列(LIS)问题"></a>[1.1]最长上升序列(LIS)问题</h3><p><strong>模型描述</strong>：给定序列A，求数值单调递增的子序列的长度最长为多少。</p>
<p><strong>例题</strong>：<a target="_blank" rel="noopener" href="https://www.luogu.org/problem/P1020">luogu P1020 导弹拦截</a>（最长<strong>不上升</strong>序列+最长<strong>上升</strong>序列）</p>
<p><strong>例题分析</strong>：</p>
<p>容易分析得到，<strong>第一问</strong>是求最长<strong>不上升</strong>序列，<strong>第二问</strong>求最长<strong>上升</strong>序列。板子题。</p>
<p>以<strong>最长上升序列</strong>为例子。</p>
<hr>
<p><strong>思路</strong>如下：</p>
<p>我们维护一个<strong>有序</strong>数列$d[i]$，用来储存一个上升序列，注意，这里的升序需要我们手动维护，不可以通过STL自动排序，否则会失去意义。</p>
<p>1-从首位开始扫描<br>2.1-当有$a[i] &gt; d[tail]$时，执行$d[++tail]=a[i]$将$a[i]$入列。<br>2.2-当有$a[i]\leq d[tail]$时，执行$d[lower_bound(d+1,d+tail+1,a[i])-(d+1)] = a[i]$将$a[i]$覆盖$d[i]$中$&gt;=a[i]$的最小整数。合理理由如下:</p>
<ul>
<li>覆盖以后依然<strong>满足升序</strong></li>
<li>覆盖后的序列与原序列相比条件更大，更容易匹配更长的序列，满足<strong>子问题最优性</strong></li>
<li>对于之后的元素，如果能跟入之前的序列，那必定也能跟入当前序列，满足<strong>无后效性</strong><br>3-扫描结束，$tail$即序列<strong>长度</strong>即为最长序列，<strong>但$d[i]$中存储的并不一定是答案的最长序列</strong></li>
</ul>
<p><strong>代码样例</strong>：</p>
<div class="hljs"><pre><code class="hljs cpp"><span class="hljs-keyword">int</span> d[<span class="hljs-number">100</span>],len = <span class="hljs-number">1</span>;
<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">LIS</span><span class="hljs-params">()</span></span>&#123;
    len = <span class="hljs-number">1</span>;
    d[<span class="hljs-number">1</span>] = a[<span class="hljs-number">1</span>];
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = <span class="hljs-number">2</span>;i &lt;= n;i++)&#123;
        <span class="hljs-keyword">if</span>(a[i] &gt; d[len]) d[++len] = a[i];
        <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(a[i] &lt;= d[len])&#123;
            <span class="hljs-keyword">int</span> pos = lower_bound(d+<span class="hljs-number">1</span>,d+len+<span class="hljs-number">1</span>,a[i]) - (d+<span class="hljs-number">1</span>) + <span class="hljs-number">1</span>;
            d[pos] = a[i];
        &#125;
    &#125;
    <span class="hljs-built_in">cout</span> &lt;&lt; len &lt;&lt; <span class="hljs-built_in">endl</span>;
&#125;
<span class="hljs-comment">//maybe出锅?</span></code></pre></div>
<hr>
<p>第一小问求的是最长<strong>不上升</strong>序列，可以类比。</p>
<p>维护一个<strong>降序序列</strong>，但是这样的话<code>upper_bound</code>/<code>lower_bound</code>就不可以直接用了，需要再传一个比较规则<code>greater&lt;int&gt;()</code>。</p>
<p>然后覆盖队列的条件也需要改，因为是<strong>不上升</strong>，用<code>lower_bound</code>会丢失答案，所以元素<strong>小于等于</strong>队尾都可以加入队尾，否则应该找一个<strong>大于</strong>它的来<strong>覆盖</strong>，即用<code>upper_bound</code>。</p>
<hr>
<p><strong>AC代码</strong>：</p>
<div class='spoiler collapsed'>
    <div class='spoiler-title'>
        Code
    </div>
    <div class='spoiler-content'>
        <div class="hljs"><pre><code class="hljs cpp"><span class="hljs-comment">//luogu P1020 导弹拦截</span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;iostream&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstring&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstdio&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;algorithm&gt;</span></span>
<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">cin</span>;<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">cout</span>;<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">endl</span>;
<span class="hljs-keyword">typedef</span> <span class="hljs-keyword">long</span> <span class="hljs-keyword">long</span> ll;
<span class="hljs-keyword">typedef</span> <span class="hljs-keyword">unsigned</span> <span class="hljs-keyword">long</span> <span class="hljs-keyword">long</span> ull;
<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::upper_bound;<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::lower_bound;
<span class="hljs-keyword">int</span> a[<span class="hljs-number">100005</span>],d1[<span class="hljs-number">100005</span>],d2[<span class="hljs-number">100005</span>],x,len1 = <span class="hljs-number">1</span>,len2 = <span class="hljs-number">1</span>,n;
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span>&#123;
      <span class="hljs-keyword">while</span>(<span class="hljs-built_in">cin</span>&gt;&gt;a[++n])&#123;
          <span class="hljs-keyword">if</span>(n == <span class="hljs-number">1</span>)&#123;d1[<span class="hljs-number">1</span>] = a[<span class="hljs-number">1</span>] , d2[<span class="hljs-number">1</span>] = a[<span class="hljs-number">1</span>] ; <span class="hljs-keyword">continue</span>;&#125;
          <span class="hljs-keyword">else</span>&#123;
              <span class="hljs-keyword">if</span>(d1[len1] &lt; a[n])&#123;
                  <span class="hljs-keyword">int</span> p = upper_bound(d1+<span class="hljs-number">1</span>,d1+len1+<span class="hljs-number">1</span>,a[n],<span class="hljs-built_in">std</span>::greater&lt;<span class="hljs-keyword">int</span>&gt;()) - d1;
                  d1[p] = a[n];
              &#125;<span class="hljs-keyword">else</span> d1[++len1] = a[n];
            <span class="hljs-keyword">if</span>(d2[len2] &gt;= a[n])&#123;
                <span class="hljs-keyword">int</span> p = lower_bound(d2+<span class="hljs-number">1</span>,d2+len2+<span class="hljs-number">1</span>,a[n]) - d2;
                d2[p] = a[n];
            &#125;<span class="hljs-keyword">else</span> d2[++len2] = a[n];
          &#125;
      &#125;
    <span class="hljs-built_in">cout</span> &lt;&lt; len1 &lt;&lt; <span class="hljs-built_in">endl</span> &lt;&lt; len2;
    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
&#125;</code></pre></div>

    </div>
</div>
<h3 id="1-2-最长公共子序列LCS"><a href="#1-2-最长公共子序列LCS" class="headerlink" title="[1.2]最长公共子序列LCS"></a>[1.2]最长公共子序列LCS</h3><p><del>虽然luogu有模板题但是luoguLCS模板的数据要求用LIS做就很艹(所以没法贴</del></p>
<p><strong>思路</strong>如下：</p>
<p>很正常的$dp$，$dp[i][j]$表示$a[1$~$i]$和$b[1$~$j]$的最大$LCS$，有转移方程：</p>
<script type="math/tex; mode=display">
dp[i][j] = max
\left\{\begin{matrix}
dp[i-1][j] &\\ 
dp[i][j-1] &\\ 
dp[i-1][j-1]+1 & 当且仅当(a[i] == b[j])
\end{matrix}\right.</script><p><strong>代码样例</strong>：</p>
<div class="hljs"><pre><code class="hljs cpp"><span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">LCS</span><span class="hljs-params">()</span></span>&#123;
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = <span class="hljs-number">1</span>;i &lt;= n;i++)&#123;
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j = <span class="hljs-number">1</span>;j &lt;= n;j++)&#123;
            dp[i][j] = dp[i<span class="hljs-number">-1</span>][j] &gt; dp[i][j<span class="hljs-number">-1</span>] ? dp[i<span class="hljs-number">-1</span>][j] : dp[i][j<span class="hljs-number">-1</span>];
            <span class="hljs-keyword">if</span>(a[i] == b[j])&#123;
                dp[i][j] = dp[i][j] &gt; dp[i<span class="hljs-number">-1</span>][j<span class="hljs-number">-1</span>]+<span class="hljs-number">1</span> ? dp[i][j] : dp[i<span class="hljs-number">-1</span>][j<span class="hljs-number">-1</span>]+<span class="hljs-number">1</span>;
            &#125;
        &#125;
    &#125;
    <span class="hljs-built_in">cout</span> &lt;&lt; dp[n][n];
&#125;</code></pre></div>
<h3 id="1-3-相关题目"><a href="#1-3-相关题目" class="headerlink" title="[1.3]相关题目"></a>[1.3]相关题目</h3><p><del><a target="_blank" rel="noopener" href="https://www.luogu.org/problem/P1439">P1439 【模板】最长公共子序列</a></del></p>
<p><del><a target="_blank" rel="noopener" href="https://www.luogu.org/problem/CF10D">CodeForces 10D</a></del></p>
<p><del><a target="_blank" rel="noopener" href="https://www.luogu.org/problem/P1216">P1216 [IOI1994][USACO1.5]数字三角形 Number Triangles</a></del></p>
<hr>
<h2 id="2-x-背包"><a href="#2-x-背包" class="headerlink" title="[2.x]背包"></a>[2.x]背包</h2><h3 id="2-1-01背包"><a href="#2-1-01背包" class="headerlink" title="[2.1]01背包"></a>[2.1]01背包</h3><p><strong>模型描述</strong>：$N$件物品，第$i$件物品的体积为$V_i$，价值为$W_i$。有一个容积为$M$的背包，要求选择一些物品放入背包，使得物品总体积不超过$M$的前提下物品的价值的和最大。（每个物品只有一个）</p>
<p><strong>思路</strong>：</p>
<p>把背包分为$n$种小背包，$dp[i]$表示放入体积$i$时最大价值为多少。有<strong>转移方程</strong>：</p>
<script type="math/tex; mode=display">
dp[i] = max
\left\{\begin{matrix}
dp[j]\\ 
dp[j-V[i]]+W[i] && 当且仅当j-V[i]\geq 0
\end{matrix}\right.</script><p>容易得到如下性质：</p>
<ul>
<li>$j$从$V[i]-&gt;M$扫描时（小到大），可能会调用刚刚更新过的背包，这就导致同一物品拿了多次，对应<strong>完全背包</strong>。</li>
<li>$j$从$M-&gt;V[i]$扫描时（大到小），必定不会调用到刚刚更新过的背包，即每个物品只会拿一次，对应<strong>01背包</strong>。</li>
</ul>
<p><strong>样例代码</strong>：</p>
<div class="hljs"><pre><code class="hljs cpp">读入;
dp[<span class="hljs-number">0</span>] = <span class="hljs-number">0</span>;
<span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = <span class="hljs-number">1</span>;i &lt;= N;i++)&#123;
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j = M;j &gt;= V[i];j--)&#123;
        dp[j] = dp[j] &gt; dp[j-V[i]] + W[i] ? dp[j] : dp[j-V[i]] + W[i];
    &#125;
&#125;
<span class="hljs-keyword">int</span> ans = <span class="hljs-number">0</span>;
<span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = <span class="hljs-number">1</span>;i &lt;= M;i++) ans = ans &gt; dp[i] ? ans : dp[i];
输出;</code></pre></div>
<h3 id="2-2-完全背包"><a href="#2-2-完全背包" class="headerlink" title="[2.2]完全背包"></a>[2.2]完全背包</h3><p><strong>模型描述</strong>：$N$件物品，第$i$件物品的体积为$V_i$，价值为$W_i$。有一个容积为$M$的背包，要求选择若干件物品放入背包，使得物品总体积不超过$M$的前提下物品的价值的和最大。（每个物品有无穷多个）</p>
<p>过程雷同01背包，更改顺序，理由见上。</p>
<div class="hljs"><pre><code class="hljs cpp">读入;
dp[<span class="hljs-number">0</span>] = <span class="hljs-number">0</span>;
<span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = <span class="hljs-number">1</span>;i &lt;= N;i++)&#123;
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j = V[i];j &lt;= M;j++)&#123;
        dp[j] = dp[j] &gt; dp[j-V[i]] + W[i] ? dp[j] : dp[j-V[i]] + W[i];
    &#125;
&#125;
<span class="hljs-keyword">int</span> ans = <span class="hljs-number">0</span>;
<span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = <span class="hljs-number">1</span>;i &lt;= M;i++) ans = ans &gt; dp[i] ? ans : dp[i];
输出;</code></pre></div>
<h3 id="2-3-多重背包"><a href="#2-3-多重背包" class="headerlink" title="[2.3]多重背包"></a>[2.3]多重背包</h3><p><strong>模型描述</strong>：$N$件物品，第$i$件物品的体积为$V_i$，价值为$W_i$，且有$C_i$个。有一个容积为$M$的背包，要求选择若干件物品放入背包，使得物品总体积不超过$M$的前提下物品的价值的和最大。（每个物品有限多个）</p>
<p><strong>思路</strong>：把$C_i$件物品当做不同的物品。朴素可做，二进制拆分和单调队列可优化。</p>
<p>暂咕</p>
<h3 id="2-4-分组背包"><a href="#2-4-分组背包" class="headerlink" title="[2.4]分组背包"></a>[2.4]分组背包</h3><p><strong>模型描述</strong>：给定$N$组物品，其中第$i$组有$C<em>i$个物品。第$i$组的第$j$个物品的体积为$V</em>{i,j}$价值为$W_{i,j}$。有一个容积为$M$的背包，要求选择若干个物品放入背包，使得每组至多选择一个物品并且物品总体积不超过$M$的前提，物品的价值总和最大。</p>
<p><strong>思路</strong>：$dp[i]$处理体积为$i$的背包。与01背包不同的是，这次01的对象被分组了，但并不影响做题过程。我们只需要一个组一个组的做就行了，但是需要注意，<strong>枚举组内对象的循环必须放在枚举背包空间的内部</strong>，这是为了维护每组只能选择一个的条件。</p>
<p><strong>样例代码</strong>：</p>
<div class="hljs"><pre><code class="hljs cpp">输入;
<span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = <span class="hljs-number">1</span>;i &lt;= N;i++)&#123;<span class="hljs-comment">//枚举组</span>
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j = M;j &gt;= <span class="hljs-number">0</span>;j--)&#123;<span class="hljs-comment">//枚举空间</span>
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> k = <span class="hljs-number">1</span>;k &lt;= C[i];k++)&#123;<span class="hljs-comment">//枚举组内物品</span>
            <span class="hljs-keyword">if</span>(j-V[k] &lt; <span class="hljs-number">0</span>) <span class="hljs-keyword">continue</span>;<span class="hljs-comment">//防炸</span>
            dp[j] = dp[j] &gt; dp[j-V[i][k]] + W[i][k] ? dp[j] : dp[j-V[i][k]] + W[i][k];
        &#125;
    &#125;
&#125;
<span class="hljs-keyword">int</span> ans = <span class="hljs-number">0</span>;
<span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = <span class="hljs-number">1</span>;i &lt;= M;i++) ans = ans &gt; dp[i] ? ans : dp[i];
输出;</code></pre></div>
<h3 id="2-5-相关题目"><a href="#2-5-相关题目" class="headerlink" title="[2.5]相关题目"></a>[2.5]相关题目</h3><p><del><a target="_blank" rel="noopener" href="https://www.luogu.org/problem/P1048">采药</a></del></p>
<p><del><a target="_blank" rel="noopener" href="https://www.luogu.org/problem/P1616">疯狂的采药</a></del></p>
<p><del><a target="_blank" rel="noopener" href="https://www.luogu.org/problem/P1757">P1757 通天之分组背包</a></del></p>
<p><del><a target="_blank" rel="noopener" href="https://www.luogu.org/record/26505544">P1064 金明的预算方案</a></del>（数据弱化的背包树形dp，可以用分类讨论+01背包过）</p>
<hr>
<h2 id="3-x-区间dp"><a href="#3-x-区间dp" class="headerlink" title="[3.x]区间dp"></a>[3.x]区间dp</h2><p>区间dp的思想是维护$dp[i][j]$，表示区间$[i,j]$内的最优解。</p>
<p>一般以<strong>区间长</strong>为<strong>阶段</strong>。</p>
<h3 id="2-1-相关题目"><a href="#2-1-相关题目" class="headerlink" title="[2.1]相关题目"></a>[2.1]相关题目</h3><p><del><a target="_blank" rel="noopener" href="https://www.luogu.org/problem/P1880">P1880 [NOI1995]石子合并</a></del></p>
<p><del><a target="_blank" rel="noopener" href="https://www.luogu.org/problem/P1063">P1063 能量项链</a></del></p>
<p><del><a target="_blank" rel="noopener" href="https://www.luogu.com.cn/problem/P1220">P1220 关路灯</a></del></p>
<p><del><a target="_blank" rel="noopener" href="https://www.luogu.com.cn/problem/P3205">P3205 [HNOI2010]合唱队</a></del></p>
<hr>
<h2 id="4-x-树形dp★"><a href="#4-x-树形dp★" class="headerlink" title="[4.x]树形dp★"></a>[4.x]<strong>树形dp</strong>★</h2><h3 id="4-1-正常树形dp"><a href="#4-1-正常树形dp" class="headerlink" title="[4.1]正常树形dp"></a>[4.1]正常树形dp</h3><p>树形dp一般以节点<strong>深度作为阶段</strong>，<strong>第一维</strong>通常记录临时<strong>根节点</strong>的编号。一般利用<strong>递归</strong>来进行<strong>规划</strong>，<strong>回溯</strong>时进行<strong>转移</strong>。</p>
<p><del><a target="_blank" rel="noopener" href="https://www.luogu.org/problem/P1352">P1352 没有上司的舞会</a></del></p>
<h3 id="4-2-背包类树形dp"><a href="#4-2-背包类树形dp" class="headerlink" title="[4.2]背包类树形dp"></a>[4.2]背包类树形dp</h3><p><del><a target="_blank" rel="noopener" href="https://www.luogu.com.cn/problem/P1272">P1272 重建道路</a></del></p>
<p>可以参考<a target="_blank" rel="noopener" href="https://weepingdemon.gitee.io/blog/2020/09/15/repLuoguP1272/">这里</a></p>
<h3 id="4-3-二次扫描与换根法"><a href="#4-3-二次扫描与换根法" class="headerlink" title="[4.3]二次扫描与换根法"></a>[4.3]二次扫描与换根法</h3><p>咕咕咕，没脑子看不懂暂时咕了</p>
<hr>
<h2 id="6-x-状压dp"><a href="#6-x-状压dp" class="headerlink" title="[6.x]状压dp"></a>[6.x]状压dp</h2><p>所谓状压$dp$，就是将$dp$状态压缩到二进制中表示，例如在图论中，用二进制第$i$位的$0 /1$来表示是否到过第$i$过点。</p>
<ul>
<li>具体的：<code>0010 0011</code> 表示该图中已经走过第$1,2,6$号点。</li>
<li>类似的，我们可以用10进制来表示一组特定序列的阿拉伯数字串：<ul>
<li><code>1314</code>可以用来表示一个$2*2$的方阵的$hash$值$(^{1　3}_{1　4})$</li>
</ul>
</li>
<li>而用二进制表示状态可以用最小的数据量表示最大的信息规模，是$10$进制存$hash$的变种</li>
</ul>
<p>这么做以后，我们可以把一整张图的信息状态存在一个整数里，这样，我们可以直接将它作为$dp$的下标进行$dp$。</p>
<p>不过状态压缩不一定是$dp$，状态压缩同样可以用在别的地方，比如标记这条路径是否可行等。</p>
<ul>
<li><strong><a target="_blank" rel="noopener" href="https://www.luogu.com.cn/problem/P1433">P1433 吃奶酪</a></strong></li>
</ul>
<p>注意到求路径可能出现小数点，所以用$double$存长度。</p>
<p>观察$n\leq15$，猜测使用状压，猜测状压表示已经走过的点。</p>
<ul>
<li>构造求距离函数<code>dis()</code></li>
<li>由小规模状态开始枚举，推导得到后一种状态<ul>
<li>枚举过程中：先找到作为当前点的$i$，再枚举作为下一个点的$j$</li>
</ul>
</li>
</ul>
<p>转移方程：</p>
<script type="math/tex; mode=display">
dp_{now | j,j} = min(dp_{now | j,j},dp_{now,i}+dis(i,j))</script><p>其中$now$为枚举的局面，$i$为我从中选出的“当前点”，$j$为我枚举出的下一个点，$dis(i,j)$为两点距离</p>
<div class='spoiler collapsed'>
    <div class='spoiler-title'>
        Code
    </div>
    <div class='spoiler-content'>
        <div class="hljs"><pre><code class="hljs cpp"><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;iostream&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstring&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstdio&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;algorithm&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cmath&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;map&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;set&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;vector&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;queue&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstdlib&gt;//rand()</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> rep(i,a,b) for(register int i = (a);i &lt;= (b);++i)</span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> per(i,a,b) for(register int i = (a);i &gt;= (b);--i)</span>
<span class="hljs-keyword">typedef</span> <span class="hljs-keyword">long</span> <span class="hljs-keyword">long</span> ll;
<span class="hljs-keyword">typedef</span> <span class="hljs-keyword">unsigned</span> <span class="hljs-keyword">long</span> <span class="hljs-keyword">long</span> ull;
<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">string</span>;<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">cin</span>;<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">cout</span>;

<span class="hljs-keyword">int</span> n;
<span class="hljs-keyword">double</span> dp[<span class="hljs-number">40000</span>][<span class="hljs-number">20</span>],inf = <span class="hljs-number">1e9</span>+<span class="hljs-number">9</span>;
<span class="hljs-class"><span class="hljs-keyword">struct</span> <span class="hljs-title">node</span>&#123;</span><span class="hljs-keyword">double</span> x,y;&#125;a[<span class="hljs-number">20</span>];

<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">double</span> <span class="hljs-title">min</span><span class="hljs-params">(<span class="hljs-keyword">double</span> x,<span class="hljs-keyword">double</span> y)</span></span>&#123;<span class="hljs-keyword">if</span>(x &lt; y) <span class="hljs-keyword">return</span> x; <span class="hljs-keyword">else</span> <span class="hljs-keyword">return</span> y;&#125;
<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">double</span> <span class="hljs-title">dis</span><span class="hljs-params">(<span class="hljs-keyword">double</span> x1,<span class="hljs-keyword">double</span> y1,<span class="hljs-keyword">double</span> x2,<span class="hljs-keyword">double</span> y2)</span></span>&#123;<span class="hljs-keyword">return</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">sqrt</span>((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));&#125;
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span>&#123;
    <span class="hljs-built_in">std</span>::ios::sync_with_stdio(<span class="hljs-number">0</span>);<span class="hljs-built_in">cin</span>.tie(<span class="hljs-number">0</span>);<span class="hljs-built_in">cout</span>.tie(<span class="hljs-number">0</span>);
    <span class="hljs-comment">//freopen(&quot;in.in&quot;, &quot;r&quot;, stdin);</span>
    <span class="hljs-built_in">cin</span> &gt;&gt; n;
    rep(i,<span class="hljs-number">1</span>,n) <span class="hljs-built_in">cin</span> &gt;&gt; a[i].x &gt;&gt; a[i].y;
    rep(i,<span class="hljs-number">0</span>,(<span class="hljs-number">1</span> &lt;&lt; n)) rep(j,<span class="hljs-number">0</span>,n+<span class="hljs-number">1</span>) dp[i][j] = inf;
    rep(i,<span class="hljs-number">1</span>,n) dp[ <span class="hljs-number">1</span> &lt;&lt; (i - <span class="hljs-number">1</span>) ][i] = dis(<span class="hljs-number">0</span>,<span class="hljs-number">0</span>,a[i].x,a[i].y);
    rep(now,<span class="hljs-number">1</span>,(<span class="hljs-number">1</span> &lt;&lt; n) - <span class="hljs-number">1</span>)&#123;
        rep(i,<span class="hljs-number">1</span>,n)&#123;
            <span class="hljs-keyword">if</span>(now &amp; (<span class="hljs-number">1</span>&lt;&lt;(i<span class="hljs-number">-1</span>)) == <span class="hljs-number">0</span>) <span class="hljs-keyword">continue</span>;
            rep(j,<span class="hljs-number">1</span>,n)&#123;
                <span class="hljs-keyword">if</span>(now &amp; (<span class="hljs-number">1</span>&lt;&lt;(j<span class="hljs-number">-1</span>)) == <span class="hljs-number">1</span>) <span class="hljs-keyword">continue</span>;
                dp[now | (<span class="hljs-number">1</span>&lt;&lt;(j<span class="hljs-number">-1</span>))][j] = <span class="hljs-built_in">std</span>::min(dp[now][i]+dis(a[i].x,a[i].y,a[j].x,a[j].y) , dp[now | (<span class="hljs-number">1</span>&lt;&lt;(j<span class="hljs-number">-1</span>))][j]);
            &#125;
        &#125;
    &#125;
    <span class="hljs-keyword">double</span> ans = inf;
    rep(i,<span class="hljs-number">1</span>,n) ans = min(ans,dp[(<span class="hljs-number">1</span> &lt;&lt; n) - <span class="hljs-number">1</span>][i]);
    <span class="hljs-built_in">printf</span>(<span class="hljs-string">&quot;%.2lf\n&quot;</span>,ans);
    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
&#125;</code></pre></div>

    </div>
</div>
<ul>
<li><strong><a target="_blank" rel="noopener" href="https://www.luogu.com.cn/problem/P5911">P5911 [POI2004]PRZ</a></strong></li>
</ul>
<p>同样，观察到$n\leq16$，猜测用二进制压缩选了人的情况</p>
<p>对于每一个局面，具有的属性有：<code>ww[now]</code>：表示局面<code>now</code>下总载重；<code>tt[now]</code>：表示局面<code>now</code>下最大用时</p>
<p>所求<code>dp[now]</code>：表示局面<code>now</code>下最小用时</p>
<p>那么，我们先枚举计算得到<code>ww[now]</code>和<code>tt[now]</code>，然后再用它们来做$dp$</p>
<p>转移方程：</p>
<script type="math/tex; mode=display">
dp_i = min(dp_i,tt_j+dp_{i\oplus j})</script><p>其中$i$为当前计算的局面，$j$为我所枚举的转移状态，也就是说我的$i$是由局面$i\oplus j$和$j$合并而来的。</p>
<div class='spoiler collapsed'>
    <div class='spoiler-title'>
        Code
    </div>
    <div class='spoiler-content'>
        <div class="hljs"><pre><code class="hljs cpp"><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;iostream&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstring&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstdio&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;algorithm&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cmath&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;map&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;set&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;vector&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;queue&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstdlib&gt;//rand()</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> rep(i,a,b) for(register int i = (a);i &lt;= (b);++i)</span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> per(i,a,b) for(register int i = (a);i &gt;= (b);--i)</span>
<span class="hljs-keyword">typedef</span> <span class="hljs-keyword">long</span> <span class="hljs-keyword">long</span> ll;
<span class="hljs-keyword">typedef</span> <span class="hljs-keyword">unsigned</span> <span class="hljs-keyword">long</span> <span class="hljs-keyword">long</span> ull;
<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">string</span>;<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">cin</span>;<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">cout</span>;

<span class="hljs-keyword">const</span> <span class="hljs-keyword">int</span> inf = <span class="hljs-number">1e9</span>+<span class="hljs-number">9</span>;
<span class="hljs-keyword">int</span> W,n,t[<span class="hljs-number">20</span>],w[<span class="hljs-number">20</span>],ans,dp[<span class="hljs-number">1</span>&lt;&lt;<span class="hljs-number">17</span>],tt[<span class="hljs-number">1</span>&lt;&lt;<span class="hljs-number">17</span>],ww[<span class="hljs-number">1</span>&lt;&lt;<span class="hljs-number">17</span>];

<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span>&#123;
    <span class="hljs-built_in">std</span>::ios::sync_with_stdio(<span class="hljs-number">0</span>);<span class="hljs-built_in">cin</span>.tie(<span class="hljs-number">0</span>);<span class="hljs-built_in">cout</span>.tie(<span class="hljs-number">0</span>);
    <span class="hljs-comment">//freopen(&quot;in.in&quot;, &quot;r&quot;, stdin);</span>
    <span class="hljs-built_in">cin</span> &gt;&gt; W &gt;&gt; n;
    rep(i,<span class="hljs-number">1</span>,n) <span class="hljs-built_in">cin</span> &gt;&gt; t[i] &gt;&gt; w[i];
    rep(i,<span class="hljs-number">0</span>,(<span class="hljs-number">1</span>&lt;&lt;n)<span class="hljs-number">-1</span>)&#123;
        dp[i] = inf;
        rep(j,<span class="hljs-number">1</span>,n)&#123;
            <span class="hljs-keyword">if</span>(i &amp; (<span class="hljs-number">1</span>&lt;&lt;(j<span class="hljs-number">-1</span>))) <span class="hljs-keyword">continue</span>;
            tt[i | (<span class="hljs-number">1</span>&lt;&lt;(j<span class="hljs-number">-1</span>))] = <span class="hljs-built_in">std</span>::max(tt[i],t[j]);
            ww[i | (<span class="hljs-number">1</span>&lt;&lt;(j<span class="hljs-number">-1</span>))] = ww[i] + w[j];
        &#125;
    &#125;
    dp[<span class="hljs-number">0</span>] = <span class="hljs-number">0</span>;
    rep(i,<span class="hljs-number">1</span>,(<span class="hljs-number">1</span>&lt;&lt;n)<span class="hljs-number">-1</span>)
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j = i;j;j = (j<span class="hljs-number">-1</span>) &amp; i)
            <span class="hljs-keyword">if</span>(ww[j] &lt;= W) dp[i] = <span class="hljs-built_in">std</span>::min(dp[i],dp[i ^ j] + tt[j]);
    <span class="hljs-built_in">cout</span> &lt;&lt; dp[(<span class="hljs-number">1</span>&lt;&lt;n)<span class="hljs-number">-1</span>] &lt;&lt; <span class="hljs-string">&quot;\n&quot;</span>;
    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
&#125;</code></pre></div>

    </div>
</div>
<ul>
<li><strong><a target="_blank" rel="noopener" href="https://www.luogu.com.cn/problem/P1879">P1879 [USACO06NOV]Corn Fields G</a></strong></li>
</ul>
<p>做的时间有点久远，等我回过头复习</p>
<div class='spoiler collapsed'>
    <div class='spoiler-title'>
        Code
    </div>
    <div class='spoiler-content'>
        <div class="hljs"><pre><code class="hljs cpp"><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;iostream&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstring&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstdio&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;algorithm&gt;</span></span>
<span class="hljs-comment">//int[1e7] ll[5*1e6]</span>
<span class="hljs-keyword">typedef</span> <span class="hljs-keyword">long</span> <span class="hljs-keyword">long</span> ll;
<span class="hljs-keyword">typedef</span> <span class="hljs-keyword">unsigned</span> <span class="hljs-keyword">long</span> <span class="hljs-keyword">long</span> ull;
<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">cin</span>;<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">cout</span>;<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">endl</span>;

<span class="hljs-keyword">int</span> dp[<span class="hljs-number">14</span>][<span class="hljs-number">1</span> &lt;&lt; <span class="hljs-number">13</span>],n,m,p,mod = <span class="hljs-number">1000000000</span>;
<span class="hljs-keyword">int</span> <span class="hljs-built_in">map</span>[<span class="hljs-number">14</span>],flag[<span class="hljs-number">1</span> &lt;&lt; <span class="hljs-number">13</span>];

<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span>&#123;

    <span class="hljs-built_in">cin</span> &gt;&gt; n &gt;&gt; m;
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">register</span> <span class="hljs-keyword">int</span> i = <span class="hljs-number">1</span>;i &lt;= n;++i)&#123;
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">register</span> <span class="hljs-keyword">int</span> j = <span class="hljs-number">1</span>;j &lt;= m;++j)&#123;
            <span class="hljs-built_in">cin</span> &gt;&gt; p;
            <span class="hljs-built_in">map</span>[i] = (<span class="hljs-built_in">map</span>[i] &lt;&lt; <span class="hljs-number">1</span>) + p;
        &#125;
    &#125;


    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">register</span> <span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>;i &lt; (<span class="hljs-number">1</span> &lt;&lt; m);++i)&#123;
        <span class="hljs-keyword">if</span>((!(i &amp; (i &gt;&gt; <span class="hljs-number">1</span>))) &amp;&amp; (!(i &amp; (i &lt;&lt; <span class="hljs-number">1</span>)))) flag[i] = <span class="hljs-number">1</span>;
        <span class="hljs-keyword">if</span>((i &amp; <span class="hljs-built_in">map</span>[<span class="hljs-number">1</span>]) == i &amp;&amp; flag[i]) dp[<span class="hljs-number">1</span>][i] = <span class="hljs-number">1</span>;
        <span class="hljs-comment">// cout &lt;&lt; dp[1][i] &lt;&lt; &quot; &quot;;</span>
    &#125;

    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">register</span> <span class="hljs-keyword">int</span> i = <span class="hljs-number">2</span>;i &lt;= n;++i)&#123;
        <span class="hljs-comment">// cout &lt;&lt; 1 &lt;&lt; &quot;\n&quot;;</span>
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">register</span> <span class="hljs-keyword">int</span> j = <span class="hljs-number">0</span>;j &lt; (<span class="hljs-number">1</span> &lt;&lt; m);++j)&#123;
            <span class="hljs-comment">// cout &lt;&lt; 2 &lt;&lt; &quot;\n&quot;;</span>
            <span class="hljs-keyword">if</span>(((<span class="hljs-built_in">map</span>[i<span class="hljs-number">-1</span>] &amp; j) == j) &amp;&amp; flag[j])&#123;
                <span class="hljs-keyword">for</span>(<span class="hljs-keyword">register</span> <span class="hljs-keyword">int</span> k = <span class="hljs-number">0</span>;k &lt; (<span class="hljs-number">1</span> &lt;&lt; m);++k)&#123;
                    <span class="hljs-keyword">if</span>(((<span class="hljs-built_in">map</span>[i] &amp; k) == k) &amp;&amp; flag[k] &amp;&amp; !(k &amp; j))&#123;
                        dp[i][k] += dp[i<span class="hljs-number">-1</span>][j];
                        dp[i][k] %= mod;
                        <span class="hljs-comment">// cout &lt;&lt; &quot;dp[i][k] = &quot; &lt;&lt; dp[i][k] &lt;&lt; &quot;\n&quot;;</span>
                    &#125;
                &#125;
            &#125;
        &#125;
    &#125;
    <span class="hljs-keyword">int</span> ans = <span class="hljs-number">0</span>;
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">register</span> <span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>;i &lt; (<span class="hljs-number">1</span> &lt;&lt; m);++i)&#123;
        ans += dp[n][i];
        ans %= mod;
    &#125;
    <span class="hljs-built_in">cout</span> &lt;&lt; ans;
    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
&#125;</code></pre></div>

    </div>
</div>
<ul>
<li><strong><a target="_blank" rel="noopener" href="https://www.luogu.com.cn/problem/P4962">P4962 朋也与光玉</a></strong></li>
</ul>
<p>老样子，看到这个十几的数字就知道该状压了，并且这次是$k\leq13$，那么很显然这里需要记录的是$k$种宝玉的状态</p>
<p>提取关键词：<strong>有向图</strong>，<strong>最短</strong>，<strong>点数为 $k$ 、恰好经过全部 $k$ 种颜色的路径</strong> </p>
<p>那么我们可以得到以下性质：我们每一次向下走的时候，不走颜色相同的，且路径有向。</p>
<p>所以大概解法就是：</p>
<ul>
<li>1.枚举起点</li>
<li>2.$dfs$向下搜索，记得剪枝</li>
</ul>
<p>这里的$dp$其实是用来剪枝的(大概)，即记忆化，这样方便找到当某一条路比之前还要劣的时候可以及时返回。</p>
<div class='spoiler collapsed'>
    <div class='spoiler-title'>
        Code
    </div>
    <div class='spoiler-content'>
        <div class="hljs"><pre><code class="hljs cpp"><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;iostream&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstring&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstdio&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;algorithm&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cmath&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;map&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;set&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;vector&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;queue&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstdlib&gt;//rand()</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> rep(i,a,b) for(register int i = (a);i &lt;= (b);++i)</span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> per(i,a,b) for(register int i = (a);i &gt;= (b);--i)</span>
<span class="hljs-keyword">typedef</span> <span class="hljs-keyword">long</span> <span class="hljs-keyword">long</span> ll;
<span class="hljs-keyword">typedef</span> <span class="hljs-keyword">unsigned</span> <span class="hljs-keyword">long</span> <span class="hljs-keyword">long</span> ull;
<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">string</span>;<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">cin</span>;<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">cout</span>;

<span class="hljs-keyword">int</span> n,m,k,a[<span class="hljs-number">111</span>],u,v,w,<span class="hljs-built_in">map</span>[<span class="hljs-number">111</span>][<span class="hljs-number">111</span>],dp[(<span class="hljs-number">1</span>&lt;&lt;<span class="hljs-number">14</span>)][<span class="hljs-number">111</span>],ans;
<span class="hljs-keyword">const</span> <span class="hljs-keyword">int</span> inf = <span class="hljs-number">2e9</span>+<span class="hljs-number">9</span>;

<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">void</span> <span class="hljs-title">dfs</span><span class="hljs-params">(<span class="hljs-keyword">int</span> p,<span class="hljs-keyword">int</span> now,<span class="hljs-keyword">int</span> sum)</span></span>&#123;
    <span class="hljs-keyword">if</span>(sum &gt;= ans || now &amp; (<span class="hljs-number">1</span>&lt;&lt;a[p]) || dp[now][p] &lt;= sum) <span class="hljs-keyword">return</span>;
    <span class="hljs-comment">//当前答案比已有答案劣，返回</span>
    <span class="hljs-comment">//当前点颜色已经被选过，返回</span>
    <span class="hljs-comment">//当前路径已经有更优的解法，返回</span>
    <span class="hljs-keyword">if</span>((now | (<span class="hljs-number">1</span>&lt;&lt;a[p])) == (<span class="hljs-number">1</span>&lt;&lt;k) - <span class="hljs-number">1</span>)&#123;
        ans = <span class="hljs-built_in">std</span>::min(ans,sum);
        <span class="hljs-keyword">return</span>;
    &#125;
    dp[now][p] = sum;
    rep(i,<span class="hljs-number">1</span>,n) <span class="hljs-keyword">if</span>(<span class="hljs-built_in">map</span>[p][i] != inf) dfs(i,now | (<span class="hljs-number">1</span>&lt;&lt;a[p]),sum + <span class="hljs-built_in">map</span>[p][i]);
    <span class="hljs-keyword">return</span>;
&#125;

<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span>&#123;
    <span class="hljs-built_in">std</span>::ios::sync_with_stdio(<span class="hljs-number">0</span>);<span class="hljs-built_in">cin</span>.tie(<span class="hljs-number">0</span>);<span class="hljs-built_in">cout</span>.tie(<span class="hljs-number">0</span>);
    <span class="hljs-comment">//freopen(&quot;in.in&quot;, &quot;r&quot;, stdin);</span>
    <span class="hljs-built_in">cin</span> &gt;&gt; n &gt;&gt; m &gt;&gt; k;
    ans = inf;
    rep(i,<span class="hljs-number">1</span>,n) <span class="hljs-built_in">cin</span> &gt;&gt; a[i];
    rep(i,<span class="hljs-number">0</span>,(<span class="hljs-number">1</span>&lt;&lt;k)<span class="hljs-number">-1</span>) rep(j,<span class="hljs-number">0</span>,n) dp[i][j] = inf;
    rep(i,<span class="hljs-number">0</span>,n) rep(j,<span class="hljs-number">0</span>,n) <span class="hljs-built_in">map</span>[i][j] = inf; 
    rep(i,<span class="hljs-number">1</span>,m)&#123;
        <span class="hljs-built_in">cin</span> &gt;&gt; u &gt;&gt; v &gt;&gt; w;
        <span class="hljs-built_in">map</span>[u][v] = w;<span class="hljs-comment">//有向边</span>
    &#125;
    rep(i,<span class="hljs-number">1</span>,n) dp[ <span class="hljs-number">1</span>&lt;&lt;a[i] ][i] = <span class="hljs-number">0</span>;<span class="hljs-comment">//选起点</span>
    ans = inf;
    rep(i,<span class="hljs-number">1</span>,n) dfs(i,<span class="hljs-number">0</span>,<span class="hljs-number">0</span>);
    <span class="hljs-keyword">if</span>(ans == inf) <span class="hljs-built_in">cout</span> &lt;&lt; <span class="hljs-string">&quot;Ushio!\n&quot;</span>;
    <span class="hljs-keyword">else</span> <span class="hljs-built_in">cout</span> &lt;&lt; ans &lt;&lt; <span class="hljs-string">&quot;\n&quot;</span>;
    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
&#125;
</code></pre></div>

    </div>
</div>
<ul>
<li><strong><a target="_blank" rel="noopener" href="https://www.luogu.com.cn/problem/P3959">P3959 宝藏</a></strong></li>
</ul>
<p>枚举起点，初始化，开始搜索，压缩当前已经到了的点的状态，记录深度，更新答案</p>
<div class='spoiler collapsed'>
    <div class='spoiler-title'>
        Code
    </div>
    <div class='spoiler-content'>
        <div class="hljs"><pre><code class="hljs cpp"><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;iostream&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstring&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstdio&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;algorithm&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cmath&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;map&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;set&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;vector&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;queue&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstdlib&gt;//rand()</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> rep(i,a,b) for(register long long i = (a);i &lt;= (b);++i)</span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> per(i,a,b) for(register long long i = (a);i &gt;= (b);--i)</span>
<span class="hljs-keyword">typedef</span> <span class="hljs-keyword">long</span> <span class="hljs-keyword">long</span> ll;
<span class="hljs-keyword">typedef</span> <span class="hljs-keyword">unsigned</span> <span class="hljs-keyword">long</span> <span class="hljs-keyword">long</span> ull;
<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">string</span>;<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">cin</span>;<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">cout</span>;

<span class="hljs-keyword">int</span> ans,n,m,dp[<span class="hljs-number">10000</span>],a[<span class="hljs-number">15</span>][<span class="hljs-number">15</span>],u,v,w,dis[<span class="hljs-number">15</span>],tmp;
<span class="hljs-keyword">int</span> inf = <span class="hljs-number">1e9</span>+<span class="hljs-number">9</span>;

<span class="hljs-function"><span class="hljs-keyword">inline</span> <span class="hljs-keyword">void</span> <span class="hljs-title">solve</span><span class="hljs-params">(<span class="hljs-keyword">int</span> now)</span></span>&#123;
    rep(i,<span class="hljs-number">1</span>,n)&#123;
        <span class="hljs-keyword">if</span>(((<span class="hljs-number">1</span> &lt;&lt; (i<span class="hljs-number">-1</span>)) &amp; now) == <span class="hljs-number">0</span>) <span class="hljs-keyword">continue</span>;
        rep(j,<span class="hljs-number">1</span>,n)&#123;
            <span class="hljs-keyword">if</span>(((<span class="hljs-number">1</span> &lt;&lt; (j<span class="hljs-number">-1</span>)) &amp; now) == <span class="hljs-number">0</span> &amp;&amp; a[i][j] != inf)&#123;
                <span class="hljs-keyword">int</span> nnow = now | (<span class="hljs-number">1</span> &lt;&lt; (j<span class="hljs-number">-1</span>));
                <span class="hljs-keyword">if</span>(dp[ nnow ] &gt; dp[now] + dis[i] * a[i][j])&#123;
                    tmp = dis[j] , dis[j] = dis[i] , ++dis[j];
                    dp[ nnow ] = dp[now] + dis[i] * a[i][j];
                    solve(nnow);
                    dis[j] = tmp;
                &#125;
            &#125;
        &#125;
    &#125;
&#125;

<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span>&#123;
    <span class="hljs-built_in">std</span>::ios::sync_with_stdio(<span class="hljs-number">0</span>);<span class="hljs-built_in">cin</span>.tie(<span class="hljs-number">0</span>);<span class="hljs-built_in">cout</span>.tie(<span class="hljs-number">0</span>);
    <span class="hljs-comment">//freopen(&quot;in.in&quot;, &quot;r&quot;, stdin);</span>
    <span class="hljs-built_in">cin</span> &gt;&gt; n &gt;&gt; m;

    ans = inf;
    rep(i,<span class="hljs-number">1</span>,n) rep(j,<span class="hljs-number">1</span>,n) a[i][j] = inf;    
    rep(i,<span class="hljs-number">1</span>,m)&#123;
        <span class="hljs-built_in">cin</span> &gt;&gt; u &gt;&gt; v &gt;&gt; w;
        a[u][v] = <span class="hljs-built_in">std</span>::min(a[u][v],w);
        a[v][u] = <span class="hljs-built_in">std</span>::min(a[v][u],w);
    &#125;
    rep(i,<span class="hljs-number">1</span>,n)&#123;
        rep(i,<span class="hljs-number">1</span>,n) dis[i] = inf;
        rep(i,<span class="hljs-number">0</span>,(<span class="hljs-number">1</span> &lt;&lt; n) - <span class="hljs-number">1</span>) dp[i] = inf;
        dis[i] = <span class="hljs-number">1</span>;
        dp[<span class="hljs-number">1</span> &lt;&lt; (i<span class="hljs-number">-1</span>)] = <span class="hljs-number">0</span>;
        solve(<span class="hljs-number">1</span> &lt;&lt; (i<span class="hljs-number">-1</span>));
        ans = <span class="hljs-built_in">std</span>::min(ans,dp[(<span class="hljs-number">1</span> &lt;&lt; n)<span class="hljs-number">-1</span>]);
    &#125;
    <span class="hljs-built_in">cout</span> &lt;&lt; ans &lt;&lt; <span class="hljs-string">&quot;\n&quot;</span>;
    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
&#125;</code></pre></div>

    </div>
</div>
<hr>
<h2 id="9-x-单调队列优化dp"><a href="#9-x-单调队列优化dp" class="headerlink" title="[9.x]单调队列优化dp"></a>[9.x]单调队列优化dp</h2><p>我们知道，<code>dp</code>的转移方程有时候会出现类似 $max(dp[i-1][k]),k\in ？$ 的情况，这时候当 $k$ 的可取范围过大时，就会出问题。</p>
<p>区间求最值，常见有 <code>线段树/树状数组</code>、<code>ST表</code>、<code>单调队列</code>。前几个由于实现过于复杂，所以我们一般使用单调队列来优化。</p>
<p>关于单调队列的相关内容，请看<strong><a target="_blank" rel="noopener" href="https://weepingdemon.gitee.io/blog/2019/11/11/algDataStructure/">这里</a>(2.1)</strong></p>
<ul>
<li>例题：</li>
</ul>
<p><a target="_blank" rel="noopener" href="https://www.luogu.com.cn/problem/P5858">P5858 「SWTR-03」Golden Sword</a></p>
<p>(最小值一开始选了<code>-1e9</code>然后WA了无数次……)</p>
<ul>
<li><code>dp</code>维护放置第<code>i</code>物品，锅内(包括将要放入的)有<code>j</code>物品的最大耐久<ul>
<li>转移方程：$dp[i][j] = max(dp[i-1][k]) + j * a[i],k\in[j-1,j+s-1]$</li>
</ul>
</li>
<li>单调队列维护 $max(dp[i-1][k]),k\in[j-1,j+s-1]$<ul>
<li>$l$ 需要维护 $k$ 的范围，$r$ 来维护单调性</li>
</ul>
</li>
</ul>
<div class='spoiler collapsed'>
    <div class='spoiler-title'>
        Code
    </div>
    <div class='spoiler-content'>
        <div class="hljs"><pre><code class="hljs cpp"><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;iostream&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstring&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstdio&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;algorithm&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cmath&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;map&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;set&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;queue&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;cstdlib&gt;//rand()</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> rep(i,a,b) for(register long long i = (a);i &lt;= (b);++i)</span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> per(i,a,b) for(register long long i = (a);i &gt;= (b);--i)</span>
<span class="hljs-keyword">typedef</span> <span class="hljs-keyword">long</span> <span class="hljs-keyword">long</span> ll;
<span class="hljs-keyword">typedef</span> <span class="hljs-keyword">unsigned</span> <span class="hljs-keyword">long</span> <span class="hljs-keyword">long</span> ull;
<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">string</span>;<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">cin</span>;<span class="hljs-keyword">using</span> <span class="hljs-built_in">std</span>::<span class="hljs-built_in">cout</span>;
ll n,w,s,dp[<span class="hljs-number">5505</span>][<span class="hljs-number">5505</span>],q[<span class="hljs-number">5555</span>],p[<span class="hljs-number">5555</span>],a[<span class="hljs-number">5555</span>],l,r,ans;
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span>&#123;
    <span class="hljs-built_in">cin</span> &gt;&gt; n &gt;&gt; w &gt;&gt; s;
    rep(i,<span class="hljs-number">1</span>,n) <span class="hljs-built_in">cin</span> &gt;&gt; a[i];
    rep(i,<span class="hljs-number">0</span>,n+<span class="hljs-number">1</span>) rep(j,<span class="hljs-number">0</span>,w+<span class="hljs-number">1</span>) dp[i][j] = <span class="hljs-number">-1e16</span>;
    dp[<span class="hljs-number">1</span>][<span class="hljs-number">1</span>] = a[<span class="hljs-number">1</span>];
    rep(i,<span class="hljs-number">2</span>,n)&#123;
        l = r = <span class="hljs-number">1</span> , q[l] = dp[i<span class="hljs-number">-1</span>][w] , p[l] = w;
        per(j,w,<span class="hljs-number">1</span>)&#123;
            <span class="hljs-keyword">while</span>(!(p[l] &lt;= j+s<span class="hljs-number">-1</span> &amp;&amp; p[l] &gt;= j<span class="hljs-number">-1</span>) &amp;&amp; l &lt;= r) ++l;
            <span class="hljs-keyword">while</span>(!(q[r] &gt;= dp[i<span class="hljs-number">-1</span>][j<span class="hljs-number">-1</span>]) &amp;&amp; l &lt;= r) --r;
            q[++r] = dp[i<span class="hljs-number">-1</span>][j<span class="hljs-number">-1</span>] , p[r] = j - <span class="hljs-number">1</span>;
            dp[i][j] = q[l] + j * a[i];
        &#125;
    &#125;
    ans = <span class="hljs-number">-1e16</span>;
    rep(i,<span class="hljs-number">1</span>,w) ans = <span class="hljs-built_in">std</span>::max(ans,dp[n][i]);
    <span class="hljs-built_in">cout</span> &lt;&lt; ans &lt;&lt; <span class="hljs-string">&quot;\n&quot;</span>;
    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
&#125;</code></pre></div>

    </div>
</div>
<link rel="stylesheet" href="/blog/css/spoiler.css" type="text/css"><script src="/blog/js/spoiler.js" type="text/javascript" async></script>
            </div>
            <hr>
            <div>
              <div class="post-metas mb-3">
                
                  <div class="post-meta mr-3">
                    <i class="iconfont icon-category"></i>
                    
                      <a class="hover-with-bg" href="/blog/categories/%E7%AE%97%E6%B3%95/">算法</a>
                    
                  </div>
                
                
                  <div class="post-meta">
                    <i class="iconfont icon-tags"></i>
                    
                      <a class="hover-with-bg" href="/blog/tags/%E7%AE%97%E6%B3%95/">算法</a>
                    
                      <a class="hover-with-bg" href="/blog/tags/%E4%BF%A1%E5%A5%A5/">信奥</a>
                    
                      <a class="hover-with-bg" href="/blog/tags/%E4%B8%93%E9%A2%98/">专题</a>
                    
                      <a class="hover-with-bg" href="/blog/tags/dp/">dp</a>
                    
                  </div>
                
              </div>
              
                <p class="note note-warning">未经允许禁止用于商业用途，转载请标注出处和作者！</p>
              
              
                <div class="post-prevnext row">
                  <article class="post-prev col-6">
                    
                    
                      <a href="/blog/2019/11/08/algSearch/">
                        <i class="iconfont icon-arrowleft"></i>
                        <span class="hidden-mobile">algorithm-搜索专题</span>
                        <span class="visible-mobile">上一篇</span>
                      </a>
                    
                  </article>
                  <article class="post-next col-6">
                    
                    
                      <a href="/blog/2019/11/07/algCppSTL/">
                        <span class="hidden-mobile">algorithm-CppSTL专题</span>
                        <span class="visible-mobile">下一篇</span>
                        <i class="iconfont icon-arrowright"></i>
                      </a>
                    
                  </article>
                </div>
              
            </div>

            
              <!-- Comments -->
              <article class="comments" id="comments">
                
                <!-- 来必力City版安装代码 -->
<div id="lv-container" data-id="city" data-uid="MTAyMC80ODI4NS8yNDc3OQ==">
  <script type="text/javascript">
     (function(d, s) {
         var j, e = d.getElementsByTagName(s)[0];
  
         if (typeof LivereTower === 'function') { return; }
  
         j = d.createElement(s);
         j.src = 'https://cdn-city.livere.com/js/embed.dist.js';
         j.async = true;
  
         e.parentNode.insertBefore(j, e);
     })(document, 'script');
  </script>
  <noscript>为正常使用来必力评论功能请激活JavaScript</noscript>
  </div>
  <!-- City版安装代码已完成 -->
              </article>
            
          </article>
        </div>
      </div>
    </div>
    
      <div class="d-none d-lg-block col-lg-2 toc-container" id="toc-ctn">
        <div id="toc">
  <p class="toc-header"><i class="iconfont icon-list"></i>&nbsp;目录</p>
  <div id="tocbot"></div>
</div>

      </div>
    
  </div>
</div>

<!-- Custom -->

  <div class="col-lg-7 mx-auto nopadding-md">
    <div class="container custom post-content mx-auto">
      <p><center><b>(っ*´Д`)っ㊖ <font color="darkblue">  疯 狂 暗 示  </font>(っ*´Д`)っ㊖</b></center></p><center><img src="https://pic.downk.cc/item/5f3bd3b414195aa59408fb13.png" srcset="/blog/img/loading.gif" width="50%" height="50%"/></center>
    </div>
  </div>


    
  </main>

  
    <a id="scroll-top-button" href="#" role="button">
      <i class="iconfont icon-arrowup" aria-hidden="true"></i>
    </a>
  

  
    <div class="modal fade" id="modalSearch" tabindex="-1" role="dialog" aria-labelledby="ModalLabel"
     aria-hidden="true">
  <div class="modal-dialog modal-dialog-scrollable modal-lg" role="document">
    <div class="modal-content">
      <div class="modal-header text-center">
        <h4 class="modal-title w-100 font-weight-bold">搜索</h4>
        <button type="button" id="local-search-close" class="close" data-dismiss="modal" aria-label="Close">
          <span aria-hidden="true">&times;</span>
        </button>
      </div>
      <div class="modal-body mx-3">
        <div class="md-form mb-5">
          <input type="text" id="local-search-input" class="form-control validate">
          <label data-error="x" data-success="v"
                 for="local-search-input">关键词</label>
        </div>
        <div class="list-group" id="local-search-result"></div>
      </div>
    </div>
  </div>
</div>
  

  
    <!-- APlayer 音乐播放器 -->
    <div id="aplayer"></div>
    <script defer src="https://cdn.staticfile.org/aplayer/1.10.1/APlayer.min.js" ></script>
<link  rel="stylesheet" href="https://cdn.staticfile.org/aplayer/1.10.1/APlayer.min.css" />
<script type="text/javascript">
  var oldLoadAp = window.onload;
  window.onload = function () {
    oldLoadAp && oldLoadAp();

    new APlayer({
      container: document.getElementById('aplayer'),
      fixed: true,
      autoplay: 'false' === 'true',
      loop: 'all',
      order: 'random',
      theme: '#708090',
      preload: 'none',
      audio: [{"name":"SLEEPWALK","artist":"冰镇豆沙君","url":"http://music.163.com/song/media/outer/url?id=1417007045.mp3","cover":"/img/cover.jpg"},{"name":"雨き声残响","artist":"冰镇豆沙君","url":"http://music.163.com/song/media/outer/url?id=1318309030.mp3","cover":"/img/cover.jpg"},{"name":"春を告げる","artist":"茶玖","url":"http://music.163.com/song/media/outer/url?id=1460240705.mp3","cover":"/img/cover.jpg"},{"name":"ベクターフィッシュ","artist":"茶玖","url":"http://music.163.com/song/media/outer/url?id=1445572300.mp3","cover":"/img/cover.jpg"},{"name":"红莲华","artist":"噢耶","url":"http://music.163.com/song/media/outer/url?id=1397590357.mp3","cover":"/img/cover.jpg"},{"name":"横竖撇点折","artist":"噢耶","url":"http://music.163.com/song/media/outer/url?id=1421414775.mp3","cover":"/img/cover.jpg"},{"name":"たぶん","artist":"真央","url":"http://music.163.com/song/media/outer/url?id=1464762744.mp3","cover":"/img/cover.jpg"},{"name":"夜に駆ける","artist":"真央","url":"http://music.163.com/song/media/outer/url?id=1461930738.mp3","cover":"/img/cover.jpg"},{"name":"Alice","artist":"yakuri","url":"http://music.163.com/song/media/outer/url?id=1431092750.mp3","cover":"/img/cover.jpg"},{"name":"起风了","artist":"yakuri","url":"http://music.163.com/song/media/outer/url?id=1367440424.mp3","cover":"/img/cover.jpg"}]
    });
  }
</script>

  

  

  <footer class="mt-5">
  <div class="text-center py-3">
    <div>
      <a href="https://hexo.io" target="_blank" rel="nofollow noopener"><span>Hexo</span></a>
      <i class="iconfont icon-love"></i>
      <a href="https://github.com/fluid-dev/hexo-theme-fluid" target="_blank" rel="nofollow noopener">
        <span>Fluid</span></a>
    </div>
    
  <div class="statistics">
    
    

    
      
        <!-- 不蒜子统计PV -->
        <span id="busuanzi_container_site_pv" style="display: none">
            总访问量 
            <span id="busuanzi_value_site_pv"></span>
             次
          </span>
      
      
        <!-- 不蒜子统计UV -->
        <span id="busuanzi_container_site_uv" style="display: none">
            总访客数 
            <span id="busuanzi_value_site_uv"></span>
             人
          </span>
      
    
  </div>


    

    
  </div>
</footer>

<!-- SCRIPTS -->
<script  src="https://cdn.staticfile.org/jquery/3.4.1/jquery.min.js" ></script>
<script  src="https://cdn.staticfile.org/twitter-bootstrap/4.4.1/js/bootstrap.min.js" ></script>
<script  src="/blog/js/debouncer.js" ></script>
<script  src="/blog/js/main.js" ></script>

<!-- Plugins -->


  
    <script  src="/blog/js/lazyload.js" ></script>
  



  <script defer src="https://cdn.staticfile.org/clipboard.js/2.0.6/clipboard.min.js" ></script>
  <script  src="/blog/js/clipboard-use.js" ></script>



  <script defer src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js" ></script>





  <script  src="https://cdn.staticfile.org/tocbot/4.11.1/tocbot.min.js" ></script>
  <script>
    $(document).ready(function () {
      var boardCtn = $('#board-ctn');
      var boardTop = boardCtn.offset().top;

      tocbot.init({
        tocSelector: '#tocbot',
        contentSelector: '#post-body',
        headingSelector: 'h1,h2,h3,h4,h5,h6',
        linkClass: 'tocbot-link',
        activeLinkClass: 'tocbot-active-link',
        listClass: 'tocbot-list',
        isCollapsedClass: 'tocbot-is-collapsed',
        collapsibleClass: 'tocbot-is-collapsible',
        collapseDepth: 6,
        scrollSmooth: true,
        headingsOffset: -boardTop
      });
      if ($('.toc-list-item').length > 0) {
        $('#toc').css('visibility', 'visible');
      }
    });
  </script>



  <script  src="https://cdn.staticfile.org/typed.js/2.0.11/typed.min.js" ></script>
  <script>
    var typed = new Typed('#subtitle', {
      strings: [
        '  ',
        "algorithm-dp动态规划专题&nbsp;",
      ],
      cursorChar: "_",
      typeSpeed: 50,
      loop: false,
    });
    typed.stop();
    $(document).ready(function () {
      $(".typed-cursor").addClass("h2");
      typed.start();
    });
  </script>





  <script  src="/blog/js/local-search.js" ></script>
  <script>
    var path = "/blog/local-search.xml";
    var inputArea = document.querySelector("#local-search-input");
    inputArea.onclick = function () {
      searchFunc(path, 'local-search-input', 'local-search-result');
      this.onclick = null
    }
  </script>



  <script  src="https://cdn.staticfile.org/fancybox/3.5.7/jquery.fancybox.min.js" ></script>
  <link  rel="stylesheet" href="https://cdn.staticfile.org/fancybox/3.5.7/jquery.fancybox.min.css" />

  <script>
    $('#post img:not(.no-zoom img, img[no-zoom]), img[zoom]').each(
      function () {
        var element = document.createElement('a');
        $(element).attr('data-fancybox', 'images');
        $(element).attr('href', $(this).attr('src'));
        $(this).wrap(element);
      }
    );
  </script>





  

  
    <!-- MathJax -->
    <script>
      MathJax = {
        tex: {
          inlineMath: [['$', '$'], ['\\(', '\\)']]
        },
        options: {
          renderActions: {
            findScript: [10, doc => {
              document.querySelectorAll('script[type^="math/tex"]').forEach(node => {
                const display = !!node.type.match(/; *mode=display/);
                const math = new doc.options.MathItem(node.textContent, doc.inputJax[0], display);
                const text = document.createTextNode('');
                node.parentNode.replaceChild(text, node);
                math.start = { node: text, delim: '', n: 0 };
                math.end = { node: text, delim: '', n: 0 };
                doc.math.push(math);
              });
            }, '', false],
            insertedScript: [200, () => {
              document.querySelectorAll('mjx-container').forEach(node => {
                let target = node.parentNode;
                if (target.nodeName.toLowerCase() === 'li') {
                  target.parentNode.classList.add('has-jax');
                }
              });
            }, '', false]
          }
        }
      };
    </script>

    <script async src="https://cdn.staticfile.org/mathjax/3.0.5/es5/tex-svg.js" ></script>

  



  
  
    <script type="text/javascript">
      //定义获取词语下标
      var a_idx = 0;
      jQuery(document).ready(function ($) {
        //点击body时触发事件
        $("body").click(function (e) {
          //需要显示的词语
          var a = new Array("富强", "民主", "文明", "和谐", "自由", "平等", "公正", "法治", "爱国", "敬业", "诚信", "友善");
          //设置词语给span标签
          var $i = $("<span/>").text(a[a_idx]);
          //下标等于原来下标+1  余 词语总数
          a_idx = (a_idx + 1) % a.length;
          //获取鼠标指针的位置，分别相对于文档的左和右边缘。
          //获取x和y的指针坐标
          var x = e.pageX, y = e.pageY;
          //在鼠标的指针的位置给$i定义的span标签添加css样式
          $i.css({
            "z-index": 999,
            "top": y - 20,
            "left": x,
            "position": "absolute",
            "font-weight": "bold",
            "color": rand_color()
          });
          // 随机颜色
          function rand_color() {
            return "rgb(" + ~~(255 * Math.random()) + "," + ~~(255 * Math.random()) + "," + ~~(255 * Math.random()) + ")"
          }
          //在body添加这个标签
          $("body").append($i);
          //animate() 方法执行 CSS 属性集的自定义动画。
          //该方法通过CSS样式将元素从一个状态改变为另一个状态。CSS属性值是逐渐改变的，这样就可以创建动画效果。
          //详情请看http://www.w3school.com.cn/jquery/effect_animate.asp
          $i.animate({
            //将原来的位置向上移动180
            "top": y - 180,
            "opacity": 0
            //1500动画的速度
          }, 1500, function () {
            //时间到了自动删除
            $i.remove();
          });
        });
      })
      ;
    </script>
  














<script src="/blog/live2dw/lib/L2Dwidget.min.js?094cbace49a39548bed64abff5988b05"></script><script>L2Dwidget.init({"pluginRootPath":"live2dw/","pluginJsPath":"lib/","pluginModelPath":"assets/","tagMode":false,"debug":false,"model":{"scale":1,"hHeadPos":0.5,"vHeadPos":0.618,"jsonPath":"/blog/live2dw/assets/assets/hijiki.model.json"},"display":{"superSample":1,"width":150,"height":300,"position":"right","hOffset":0,"vOffset":-20},"mobile":{"show":true,"scale":1},"react":{"opacityDefault":0.7,"opacityOnHover":0.2},"log":false});</script></body>
</html>
